package main

import (
	"fmt"
	"sort"
)

func main() {
	arr := []int{1211, 212134, 172, 966, 111}
    //BEGIN->离散化代码
	bak := make([]int, len(arr))
	copy(bak, arr)
	sort.Ints(bak)  //排序
    unique(&bak) //去重
	Len:=len(arr)
	myTree := InitTree(len(bak)-1)  //构建一个空的权值线段树
    for i:=0; i<Len; i++ {
        //END->离散化代码
		myTree.UpDate(lower_bound(bak, arr[i]), 1)  //二分查找arr[i] 在bak数组中的下标位置
    }
	fmt.Println(bak[myTree.Kth(3)]) //查找第3大
}

type node struct {  //线段树结构
	val []struct {
		sum, l, r int   //sum 值的次数   l, r 左右区间
	}
}

//初始化建立一个空树, 需要传入一个值域的最大值, 开辟空间建一个空的权值线段树
func InitTree(maxVal int) *node {
	tree := &node{make([]struct{sum, l, r int}, maxVal << 2)}
	tree.buildTree(1, 0, maxVal)
	return tree
}
func (this *node) buildTree(rt, le, ri int) {
	this.val[rt].l, this.val[rt].r = le, ri
	if le == ri {return}
	mid := (le + ri) >> 1
	this.buildTree(rt<<1, le, mid)
	this.buildTree(rt<<1|1, mid+1, ri)
}

/*
	查询所有数的第k大值, 第k小值
	这是权值线段树的核心，思想如下(以第k大举例子):
	到每个节点时，如果右子树的总和大于等于k，说明第k 大值出现在右子树中，则递归进右子树；否则说明此时的第k 大值在左子树中，则递归进左子树	 注意：此时要将k 的值减去右子树的总和。
	如果我们要找的是第7 大值，右子树总和为4 ，7−4=3 ，说明在该节点的第7 大值在左子树中是第3 大值。
	最后一直递归到只有一个数时，那个数就是答案。
*/
func (this *node) Kth(k int) int {
	return this.kth(1, k)
}
func (this *node) kth(rt, k int) int {
	if this.val[rt].l == this.val[rt].r {return this.val[rt].l}
	rtle, rtri := rt<<1, rt<<1|1
	if k <= this.val[rtri].sum {
		return this.kth(rtri, k)
	} else {
		return this.kth(rtle, k-this.val[rtri].sum)
	}
}

//单点修改 (单个数出现的次数+1) x为更新哪个数, p=1 就是增加x -1就是删除x
func (this *node) UpDate(x, p int) {
	this.update(1, x, p)
}
func (this *node) update(rt, x, p int) {
	if this.val[rt].l == this.val[rt].r {
		this.val[rt].sum += p
		return
	}
	mid := (this.val[rt].l + this.val[rt].r) >> 1
	rtle, rtri := rt<<1, rt<<1|1
	if x <= mid {this.update(rtle, x, p)} else {
		this.update(rtri, x, p)
	}
	this.val[rt].sum = this.val[rtle].sum + this.val[rtri].sum
}

//查询整个值域区间查询某个数出现的次数
func (this *node) QueryCount(val int) int {
	return this.queryCount(1, val)
}
func (this *node) queryCount(rt, val int) int {
	if this.val[rt].l == this.val[rt].r {return this.val[rt].sum}
	mid := (this.val[rt].l + this.val[rt].r) >> 1
	if val <= mid {return this.queryCount(rt<<1, val)}
	if val > mid {return this.queryCount(rt<<1|1, val)}
	return 0
}

//查询一个数的排名
func (this *node) QueryKth(val int) int {
    return this.QuerySpace(0, val-1) + 1
}

//查询一段值域区间出现的次数
func (this *node) QuerySpace(left, right int) int {
	return this.querySpace(1, left, right)
}
func (this *node) querySpace(rt, left, right int) int {
	if this.val[rt].l == left && this.val[rt].r == right {
		return this.val[rt].sum
	}
	mid, rtle, rtri := (this.val[rt].l + this.val[rt].r) >> 1, rt<<1, rt<<1|1
	if right <= mid {
		return this.querySpace(rtle, left, right)
	}else if left > mid {
		return this.querySpace(rtri, left, right)
	} else {
		return this.querySpace(rtle, left, mid) + this.querySpace(rtri, mid+1, right)
	}
}

//离散化函数
//去重
func unique(arr *[]int) {
    slow, fast, Len := 0, 1, len(*arr)
    for fast < Len {
        if (*arr)[slow] != (*arr)[fast] {
            slow++
            (*arr)[slow] = (*arr)[fast]
        }
        fast++
    }
    *arr=(*arr)[:slow+1]
}
//二分
func lower_bound(arr []int, x int) int {
        left, right := 0, len(arr)-1
        for left <= right {
            mid := (right + left) >> 1
            if arr[mid] == x {
                return mid
            } else if arr[mid] > x {
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return -1
}